import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

/*
 * @lc app=leetcode.cn id=653 lang=java
 *
 * [653] 两数之和 IV - 输入 BST
 *
 * https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst/description/
 *
 * algorithms
 * Easy (60.22%)
 * Likes:    304
 * Dislikes: 0
 * Total Accepted:    48.2K
 * Total Submissions: 79.9K
 * Testcase Example:  '[5,3,6,2,4,null,7]\n9'
 *
 * 给定一个二叉搜索树 root 和一个目标结果 k，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入: root = [5,3,6,2,4,null,7], k = 9
 * 输出: true
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入: root = [5,3,6,2,4,null,7], k = 28
 * 输出: false
 * 
 * 
 * 示例 3：
 * 
 * 
 * 输入: root = [2,1,3], k = 4
 * 输出: true
 * 
 * 
 * 示例 4：
 * 
 * 
 * 输入: root = [2,1,3], k = 1
 * 输出: false
 * 
 * 
 * 示例 5：
 * 
 * 
 * 输入: root = [2,1,3], k = 3
 * 输出: true
 * 
 * 
 * 
 * 
 * 提示:
 * 
 * 
 * 二叉树的节点个数的范围是  [1, 10^4].
 * -10^4 
 * root 为二叉搜索树
 * -10^5 
 * 
 * 
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    // 中序迭代遍历 + Set
    public boolean findTarget(TreeNode root, int k) {
        boolean ret = false;
        Set<Integer> hashSet = new HashSet<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode p = root;
        while (p != null || !stack.empty()) {
            // 一只
            if(p != null) {
                stack.push(p);
                p = p.left;
            } else {
                TreeNode treeNode = stack.pop();
                // 左孩子全部入栈后
                // 如果集合里存在对应值
                if (hashSet.contains(treeNode.val)) {
                    ret = true;
                    break;
                }
                // 将另一个节点的值存入集合
                hashSet.add(k - treeNode.val);
                p = treeNode.right;   
            }
        }
        return ret;
    }

}
// @lc code=end

